package 二叉树.BinaryTreeHorizonTravel;

import 二叉树.BinaryTreeTemplate;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 此文件专门用于二叉树的层次遍历
 *
 * 说明:
 * A逻辑 和中左右的递归差不多 只不过在输出的时候要放入对应层次的[nowLevel用于记录节点所属的层次]
 * B 传入的树例子:
 *         1
 *       /   \
 *      2     3
 *     / \   / \
 *    4   5 6   7
 * 输出的结果: 123456
 * C
 */

public class BinaryTreeHorizonTravel {

    //结果集
    private List<List<Integer>> resultList = new ArrayList<>();

    /**
     * 层次遍历-递归法
     */
    public void DG(BinaryTreeTemplate nowLevelNode, int nowLevel) {
        if (nowLevelNode == null) return;
        nowLevel++;
        if (resultList.size() < nowLevel) {
            List<Integer> nowLevelList = new ArrayList<>();
            nowLevelList.add(nowLevelNode.value);
            resultList.add(nowLevelList);
        } else {
            resultList.get(nowLevel - 1).add(nowLevelNode.value);
        }
        DG(nowLevelNode.left, nowLevel);
        DG(nowLevelNode.right, nowLevel);
    }

    /**
     * 层次遍历-迭代法
     */
    public List<List<Integer>> DD(BinaryTreeTemplate startLevelNode){
        Queue<BinaryTreeTemplate> queue = new LinkedList();
        if(startLevelNode == null) return resultList;
        queue.add(startLevelNode);
        while(!queue.isEmpty()){
            List<Integer> nowLevelList = new ArrayList<>();
            int nowLevelValueCounts = queue.size();
            while (nowLevelValueCounts > 0){
                BinaryTreeTemplate nowLevelNodes = queue.poll();
                nowLevelList.add(nowLevelNodes.value);
                if (nowLevelNodes.left != null){queue.offer(nowLevelNodes.left);}
                if (nowLevelNodes.right != null){queue.offer(nowLevelNodes.right);}
                nowLevelValueCounts--;
            }
            resultList.add(nowLevelList);
        }
        return resultList;
    }

    //test
    public static void main(String[] args) {
        BinaryTreeTemplate tree = BinaryTreeTemplate.createCompleteBinaryTree();
        BinaryTreeHorizonTravel travel = new BinaryTreeHorizonTravel();

        travel.DD(tree);
        System.out.println(travel.resultList);
    }
}